package mid.class1;

/**
 *
 * https://leetcode.cn/problems/implement-trie-prefix-tree/description/
 * 前缀树问题
 * -1
 * a  b  f
 * b c  c d n
 * c  d  f  e d
 */
public class Code02_TrieTree {
    public static void main(String[] args) {
        String[] arr = {"abc", "bck", "abd", "ace", "abd"};
        Trie trie = new Trie();
        for (int i = 0; i < arr.length; i++) {
            trie.insert(arr[i]);
        }
        int count = trie.searchKey("abd");
        System.out.println(count);
        int i = trie.prefixNumber("ab");
        System.out.println("i = " + i);

        trie.delete("abd");
        count = trie.searchKey("abd");
        System.out.println(count);
    }

    public static class Trie {
        private Node root = new Node();

        public void delete(String key) {
            if (searchKey(key) != 0) {
                Node cur = this.root;
                cur.pass--;
                char[] arr = key.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    int index = arr[i] - 'a';
                    if (--cur.nexts[index].pass == 0) {
                        cur.nexts[index] = null; // 删除后不继续执行
                        return ; //
                    }
                    cur = cur.nexts[index];
                }
                cur.end--;
            }
        }

        // 最大前缀数量
        public int prefixNumber(String prefix) {
            if (prefix == null || prefix.length() == 0) return 0;
            char[] arr = prefix.toCharArray();
            Node cur = this.root;
            for (int i = 0; i < arr.length; i++) {
                int index = arr[i] - 'a';
                if (cur.nexts[index] == null) {
                    return 0;
                }
                cur = cur.nexts[index];
            }
            return cur.pass;
        }

        // 查询key
        public int searchKey(String key) {
            if (key == null || key.length() == 0) return 0;
            Node cur = this.root;
            char[] arr = key.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                int index = arr[i] - 'a';
                if (cur.nexts[index] == null) {
                    return 0;
                }
                cur = cur.nexts[index];
            }
            return cur.pass;
        }

        // 插入key
        public void insert(String path) {
            if (path == null || path.length() == 0) return;
            Node cur = this.root;
            char[] arr = path.toCharArray();
            cur.pass++;
            for (int i = 0; i < arr.length; i++) {
                int index = arr[i] - 'a';
                if (cur.nexts[index] == null) {
                    cur.nexts[index] = new Node();
                }
                cur = cur.nexts[index];
                cur.pass++;
            }
            cur.end++;
        }
    }

    public static class Node {
        public int pass;
        public int end;
        public Node[] nexts;

        public Node() {
            this.pass = 0;
            this.end = 0;
            this.nexts = new Node[26];
        }
    }
}
